/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2022-07-25
 * Time: 8:02
 */

public class SingalList {
    //构建一个节点类
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    //斗节点引用
    public ListNode head;

//    //通过穷举的方式 创建一个链表出来
//    public void creatList(){
//        Node node1 = new Node(12);
//        Node node2 = new Node(10);
//        Node node3 = new Node(23);
//        Node node4 = new Node(34);
//        //将这些节点连接起来
//        node1.next=node2;
//        node2.next=node3;
//        node3.next=node4;
//        //斗节点引用
//        head=node1;
//    }
    //打印链表
public void display(){
    if(this.head == null){
        System.out.println("单链表为空");
    }
        ListNode cur = head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    System.out.println();

}
//查找关键key是否存在
    public boolean findKey(int key){
        ListNode cur = head;
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur=cur.next;
        }
        return false;

    }
//得到链表长度 用计数器count
    public int size(){
        ListNode cur = head;
        int count = 0;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    /**
     * 插入 任意位置找插入点前驱
     * 头插、尾插、任意位置插
     */
    //头插 不用移动元素 时间复杂度为O(1)
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next=head;
        head = node;
    }
    //尾插 遍历了链表 时间复杂度是O(n)
    public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = head;
        while (cur.next!= null){
            cur= cur.next;
        }
        cur.next = node;
    }

    //任意位置index插
    //检查index是否合法
    private void checkIndex(int index){
        if(index<0 || index>size()){
            throw new IndexNotLegalException();
        }
    }
    //找到index的前驱
    private ListNode findIndexSubOfOne(int index){
        ListNode cur = head;
        while (index -1 != 0){
            cur= cur.next;
            index--;
        }
        return cur;

    }
    public void addIndex(int index,int data){
        //检查Index是否合法
        checkIndex(index);
        //index==0 头插
        if(index == 0){
            addFirst(data);
            return;
        }
        //index == size() 尾插
        if(index==size()){
            addLast(data);
            return;
        }
        //既不是头部也不是尾部且index的位置合法在index处插入
        ListNode cur = findIndexSubOfOne(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }
/**
 * 删除
 * 1.删除第一次出现关键字为key的节点
 * 2.删除所有值为key的节点
 */
//1.删除第一次出现关键字为key的节点
//找到删除点前驱
private ListNode searchPre(int key){
    ListNode cur = this.head;
    while (cur.next!=null){
        if(cur.next.val== key){
            return cur;
        }
        cur = cur.next;
    }
    return null;
}
public void remove(int key){
    //如果key为头结点
    if(key == head.val){
        head=head.next;
    }else {
        //如果key不为头结点，遍历列表找到头结点的前驱
        ListNode cur = searchPre(key);
        if(cur == null){
            return;
        }
        cur.next = cur.next.next;
    }


}
//2.删除所有值为key的节点
    public void removeAllKey(int key) {

        ListNode cur = head.next;
        ListNode prev = head;
        while (cur!=null){
            if (key == cur.val) {
                prev.next = cur.next;
                cur = cur.next;

            }else {
                prev=cur;
                cur=cur.next;
            }
        }
        if(key == head.val){
           head = head.next;
        }

    }
    //3.清空单链表
    public void clear(){
    this.head=null;
    }

    public ListNode FindKthToTail(ListNode head, int k) {
        if(k<0 || head == null){
            return null;
    }
        ListNode fast = head;
        ListNode slow = head;
        while (k-1!=0){
            if(fast == null){
                return null;
            }
            fast = fast.next;
            k--;
        }
        while (fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }

}
